import javax.swing.tree.TreeNode;
import java.util.List;
import java.util.Stack;

public class Test {
    //找到p、q的最近公共祖先
    //1
    public BinaryTree.TreeNode lowestCommonAncestor(BinaryTree.TreeNode root, TreeNode p, TreeNode q) {
        //1、p在root的左边，q在root的右边   最近公共祖先是root
        //2、p和q在root的同一边
        //3、p == root || q == root        最近公共祖先是root
        if(root == null) return null;
        if(p == root || q == root)return root;
        BinaryTree.TreeNode leftTree = lowestCommonAncestor(root.left,p,q);
        BinaryTree.TreeNode rightTree = lowestCommonAncestor(root.right,p,q);
        if(leftTree != null && rightTree != null){
            return root;
        }else if(leftTree != null){
            return leftTree;
        }else{
            return rightTree;
        }
    }
    //2
    public BinaryTree.TreeNode lowestCommonAncestor(BinaryTree.TreeNode root, BinaryTree.TreeNode p, BinaryTree.TreeNode q) {
        //如果二叉树保留了父亲节点的地址，那么这个题可转变为求链表的相交节点
        //可以使用栈存储，先出差值个，然后同时出，相同的那个就是最近祖先
        //难点：如何找到根节点到指定节点路径上的所有节点
        if(root == null){
            return null;
        }
        Stack<BinaryTree.TreeNode> stackP = new Stack<>();
        Stack<BinaryTree.TreeNode> stackQ = new Stack<>();
        getPath(root,p,stackP);
        getPath(root,q,stackQ);

        //对栈的操作
        int sizeP = stackP.size();
        int sizeQ = stackQ.size();
        //让长度长的栈先出差值个元素
        if(sizeP > sizeQ){
            int size = sizeP - sizeQ;
            while(size != 0){
                stackP.pop();
                size--;
            }
        }else{
            int size = sizeQ - sizeP;
            while(size != 0){
                stackQ.pop();
                size--;
            }
        }
        //两个栈元素是相同的
        while(!stackP.isEmpty() && !stackQ.isEmpty()){
            //找到相交的节点返回就是最近的祖先
            //注意栈里存放的是对象的引用
            if(stackP.peek().equals(stackQ.peek())){
                return stackP.peek();
            }
            stackP.pop();
            stackQ.pop();
        }
        return null;
    }
    //找到root到node路径上的所有节点存储到stack中
    public boolean getPath(BinaryTree.TreeNode root,BinaryTree.TreeNode node,Stack<BinaryTree.TreeNode> stack){
        if(root == null || node == null){
            return false;
        }
        //先将遍历到的节点入栈，再进行判断
        stack.push(root);
        if(root == node){//说明root已经找到当前的节点了
            return true;
        }
        boolean flg = getPath(root.left,node,stack);
        if(flg){
            return true;
        }
        boolean flg2 = getPath(root.right,node,stack);
        if(flg2){
            return true;
        }
        //如果左右都没找到说明一定不是你路径上的节点
        //那么就出栈并且返回flase
        stack.pop();
        return false;
    }
    //判断subRoot是否为root的子树
    //root:s subRoot:r 时间复杂度：r*s（每个节点都需要判断是否与subRoot相同）
    public boolean isSubtree(BinaryTree.TreeNode root, BinaryTree.TreeNode subRoot) {
        //1、根节点和子树相不相同
        //2、subRoot是不是root.left的子树
        //3、subRoot是不是 root.right的子树
        if(isSameTree(root,subRoot)){
            return true;
        }
        //判断root是否为空，防止空指针异常
        if(root == null){
            return false;
        }
        //判断左节点
        if(isSubtree(root.left,subRoot)){
            return true;
        }
        //判断右节点
        if(isSubtree(root.right,subRoot)){
            return true;
        }
        return false;
    }
    //判断两棵树是否为相同树
    //时间复杂度：设p有M个元素，q有N个元素，时间复杂度为min（m，n）;
    public boolean isSameTree(BinaryTree.TreeNode p, BinaryTree.TreeNode q) {
    //1、一颗树为空一棵树不为空
    //2、虽然两棵树都不为空但是值不相同
    //建议采用前序遍历：根左右
    if(p == null && q != null || q == null && p != null){
        return false;
    }
    //两个都为空认为是两棵相同的树
    if(p == null && q== null){
        return true;
    }
    //两个都不为空
    if(p.val != q.val) return false;
    //左树和右树均为true则是两颗相同的树
    return isSameTree(p.left,q.left)
            && isSameTree(p.right,q.right);
}
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        BinaryTree.TreeNode root = binaryTree.creatTree();//静态内部类的调用
       /* //前序遍历
        binaryTree.preOrder(root);
        System.out.println();
        //中序遍历
        binaryTree.inOrder(root);
        System.out.println();
        //后序遍历
        binaryTree.postOrder(root);*/
        List<BinaryTree.TreeNode> list = binaryTree.preOrder2(root);
        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i).val + " ");
        }
        System.out.println();
        for(BinaryTree.TreeNode x:list){
            System.out.print(x.val + " ");
        }
        System.out.println();
        System.out.println("树的节点个数："+binaryTree.size(root));
        System.out.println("树的节点个数2："+binaryTree.size2(root));
        System.out.println("叶子节点个数："+binaryTree.getLeafNodeCount(root));
        System.out.println("第三层的节点个数："+binaryTree.getKLevelNodeCount(root, 3));
        System.out.println("二叉树的深度：" + binaryTree.getHeight(root));
        boolean ret = binaryTree.find(root,'E');
        if(ret == true){
            System.out.println("存在值为E的节点");
        }else{
            System.out.println("没有值为E的节点");
        }
        System.out.print("层序遍历：");
      binaryTree.levelOrder(root);
        System.out.println();
        boolean ret1 = binaryTree.isCompleteTree(root);
        if(ret1){
            System.out.println("该树是完全二叉树");
        }else{
            System.out.println("该树不是完全二叉树");
        }

        }
    }

